import java.util.Arrays;

/**
 * @author hewei
 * @version 1.0
 * @description: 1706. 球会落何处
 * @date 2022/10/13 16:26
 */

public class FindBall {

    int[][] temp;
    int m;
    int n;
    int[][] grid;
    int[] ans;
    public int[] findBall(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        temp = new int[m][n];
        ans = new int[n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(temp[i], -1);
        }
        for (int i = 0; i < n; i++) {
            ans[i] = process(0, i, i);
        }
        return ans;
    }

    public int process(int i, int j, int index) {
        if (i == m - 1) {
            return (j + grid[i][j] < 0 || j + grid[i][j] >= n || grid[i][j] != grid[i][j + grid[i][j]]) ? -1 : j + grid[i][j];
        }
        if (temp[i][j] != -1) return ans[temp[i][j]];
        temp[i][j] = index;
        int x;
        int y;
        if (grid[i][j] == -1) {
            if (j == 0 || grid[i][j - 1] == 1) return -1;
            x = i + 1;
            y = j - 1;
        } else {
            if (j == n - 1 || grid[i][j + 1] == -1) return -1;
            x = i + 1;
            y = j + 1;
        }
        return process(x, y, index);
    }
}
